def Merge(nums: list, left, mid, right):
    i = left
    j = mid + 1
    temp = []
    while i <= mid and j <= right:
        if nums[i - 1] < nums[j - 1]:
            temp.append(nums[i - 1])
            i += 1
        else:
            temp.append(nums[j - 1])
            j += 1
    if i <= mid:
        temp.extend(nums[i - 1 : mid])

    if j <= right:
        temp.extend(nums[j - 1 : right])
    nums[left - 1 : right] = temp
    return nums


def MergeSort(nums, left, right):
    if left == right:
        return nums
    mid = (left + right) // 2
    nums = MergeSort(nums, left, mid)
    nums = MergeSort(nums, mid + 1, right)
    nums = Merge(nums, left, mid, right)
    return nums

if __name__ == "__main__":
    nums = [50, 10, 90, 30, 70, 40, 80, 60, 20]
    nums = MergeSort(nums, 1, len(nums))
    print(nums)
    pass
